\documentclass[unicode]{beamer}
\mode<presentation>
\usepackage{beamerthemesplit}
\usetheme{Malmoe}
%\usepackage[cp1251]{inputenc}
\usepackage[english]{babel}
\usepackage[T2A]{fontenc}
\usepackage{amssymb,amsfonts,amsmath}
\usepackage {array}
\usepackage{graphicx}
\usepackage {gastex}
\usepackage{algorithm,algpseudocode}
\usepackage[]{color}%,dvips
\usepackage{pstricks,pst-node,pst-text}%,pst-3d
\definecolor{dred}{rgb}{0.6, 0, 0}

\expandafter\def\expandafter\insertshorttitle\expandafter{%
  \insertshorttitle\hfill%
  \insertframenumber\,/\,\inserttotalframenumber}

\def\append{{\bf append}}
\def\iappend{{\bf iappend}}
\def\len{{\bf len}}
\def\nextPal{{\bf nextPal}}
\def\maxPal{{\bf maxPal}}
\def\Pal{{Pal}}
\algtext*{EndWhile}% Remove "end while" text
\algtext*{EndIf}% Remove "end if" text
\algtext*{EndFunction}% Remove "end function" text
\algtext*{EndProcedure}% Remove "end procedure" text
\algtext*{EndFor}% Remove "end for" text

\let\OldComment\Comment
\renewcommand{\Comment}[1]{\OldComment{\textcolor{gray}{#1}}}


\author[Dmitry Kosolobov]{Dmitry Kosolobov}
\title{Online Detection of Repetitions with Backtracking}

\institute[]{Ural Federal University\\ Ekaterinburg, Russia}
\begin{document}
\date{ }
\maketitle

\section{Introduction}

\begin{frame}
\frametitle{Repetitions}
\visible<2->{
\begin{block}{Definitions}
\begin{itemize}
\item<2-> $p$ is a \emph{period of $w$} if $w[i] = w[i{+}p]$ for $i = 0,1,\ldots,|w|{-}1{-}p$
\item<3-> $|w|/p$ is the \emph{exponent of $w$}, where $p$ is the minimal period of $w$
\item<4-> $w$ is an \emph{$e$-repetition} if its exponent is greater than or equal to $e$
\item<5-> $w$ is \emph{$e$-repetition-free} if $w$ does not contain an $e$-repetition as a substring
\end{itemize}
\end{block}
}
\visible<6->{
\begin{block}{Example}
$
\begin{array}{r|c|c}
\text{text} & \text{minimal period} & \text{exponent} \\
\hline
\visible<7->{\visible<7->{abb\cdot abb} &\visible<8->{3}&\visible<9->{2}\\}% & \visible<10->{\text{ is a }2\text{-repetition}}\\}
\visible<10->{\visible<10->{ab\cdot ab\cdot a}  &\visible<11->{2}&\visible<12->{2.5}\\}% & \visible<14->{\text{ is a }2\text{-repetition}}\\}
\visible<13->{\visible<13->{ab\cdot ab\cdot ab} &\visible<14->{2}&\visible<15->{3} \\}% & \visible<18->{\text{ is a }3\text{-repetition}}\\}
\visible<16->{\visible<16->{abbbb\cdot abb}     &\visible<17->{5}&\visible<18->{1.6}}% & \visible<22->{\text{ is a }1.5\text{-repetition}}}
\end{array}
$
\end{block}
}
\end{frame}

\iffalse
\begin{frame}
\frametitle{Repetition-free strings}
\visible<2->{
\begin{block}{Definitions}
\begin{itemize}
\item<2-> $w[i..j] = w[i]w[i{+}1]\cdots w[j]$ is a \emph{substring} or a \emph{factor} of $w$
\item<3-> $w$ is \emph{$e$-repetition-free} if $w$ does not contain an $e$-repetition as a substring
\end{itemize}
\end{block}
}
\visible<4->{
\begin{block}{Example}
$
\begin{array}{l}
{\color<5,13,19,23>{red}a}{\color<5,6,13,14,19,20,23,24>{red}b}{\color<6,7,13,14,15,19,20,21,23,24>{red}c}%
{\color<7,8,13,14,15,16,19,20,21,22,23,24>{red}b}{\color<8,9,14,15,16,17,19,20,21,22,23,24>{red}a}%
{\color<9,10,15,16,17,18,19,20,21,22,23,24>{red}c}{\color<10,11,16,17,18,20,21,22,23,24>{red}b}%
{\color<11,12,17,18,21,22,23,24>{red}c}{\color<12,18,22,24>{red}a}\text{ is }2\text{-repetition-free}\\
\invisible{L}\only<5-12>{2\text{-repetitions of period }1}\only<13-18>{2\text{-repetitions of period }2}%
\only<19-22>{2\text{-repetitions of period }3}\only<23-24>{2\text{-repetitions of period }4}
\end{array}
$
\end{block}
}
\end{frame}
\fi

\begin{frame}
\frametitle{Problem and known solutions}
\visible<2->{Fix a rational $e > 1$\\}
\visible<3->{Maintain a string $t$ (initially empty) under the following operations:}
\begin{itemize}
\item<4-> $\mathit{append}(c)$: append a letter $c$ to the right of $t$
\item<5-> $\mathit{backtrack}$: remove the last letter of $t$
\item<6-> $\mathit{repfree}$: check whether $t$ is $e$-repetition-free
\end{itemize}
\visible<7->{This structure is called \emph{$e$-repetition detector}}
\visible<8->{
\begin{block}{Results without backtracking ($n$ is the number of operations)}
\begin{itemize}
\item<9-> $\Omega(n\log n)$ unordered alphabet [Main, Lorentz 85]
\item<10-> $\Theta(n\log n)$ $e{=}2$, unordered alphabet [Apostolico, Breslauer 96]
\item<11-> $O(n\log\sigma)$ ordered alphabet [Hong, Chen 08] ($\sigma$~is~the~alphabet~size)
\end{itemize}
\end{block}
}
\end{frame}

\begin{frame}
\frametitle{Contribution}
\pause
Fix a rational $e > 1$
\pause
\begin{block}{Theorem 1}
For unordered alphabet, there is an $e$-repetition detector working in $O(n\log m)$ time and $O(m)$ space, where $m$ is the length of a longest string generated by a given sequence of $n$ $\mathit{append}$ and $\mathit{backtrack}$ operations.
\end{block}
\pause
\begin{block}{Theorem 2 (our method differs from [Hong, Chen 08])}
For ordered alphabet, there is an $e$-repetition detector without backtracking working in $O(n\log\sigma)$ time and $O(n)$ space, where $n$ is the number of $\mathit{append}$ operations and $\sigma$ is the alphabet size.
\end{block}
\end{frame}


\section{Catchers}

\subsection{Catchers}

\begin{frame}
\frametitle{Catcher}
\begin{itemize}
\item<2-14> fix a rational $e > 1$
\item<3-14> catcher ``catches'' $e$-repetitions in $t$
\item<4-14> catcher is defined by integers $i$ and $j$ ($0 \le i \le j < |t|$)
\item<5-14> catcher searches the string $t[i..j]$
\item<6-14> catcher finds $e$-repetitions using occurrences of $t[i..j]$
\end{itemize}
\begin{picture}(108,23)(0,0)
\gasset{Nw=12,Nh=12,Nframe=n,AHnb=0}
%\visible<7>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{observe1}}}
%\visible<8>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{observe2}}}
%\visible<9>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{observe3}}}
\visible<7>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{work1}}}
\visible<8>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{work2}}}
\visible<9>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{work3}}}
\visible<10>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{work4}}}
\visible<11>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{work5}}}
\visible<12>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{work6}}}
\visible<13,14>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{work7}}}
\visible<15>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{spider1}}}
\visible<16>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{spider2}}}
\visible<17>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{spider3}}}
\visible<18->{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{spider4}}}
\end{picture}
\visible<14->{
\begin{block}{Lemma}
If $t[k..n]$ is an $e$-repetition and $n - e(n{-}j) \le k \le i$, the catcher finds this repetition.
\end{block}
}
\end{frame}

\subsection{Backtracking in catchers}

\begin{frame}
\frametitle{Backtracking}
\begin{itemize}
\item<2-> catcher uses constant space real-time string searching
\item<3-> catcher saves its states in an array
\item<4-> backtracking restores a previous state from that array
\end{itemize}
\begin{picture}(108,25)(0,0)
\gasset{Nw=12,Nh=12,Nframe=n,AHnb=0}
\visible<5>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states0}}}
\visible<6>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states1}}}
\visible<7>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states2}}}
%\visible<8>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states3}}} %duplicated
\visible<8>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states4}}}
\visible<9>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states5}}}
\visible<10>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states6}}}
\visible<11>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states7}}}
\visible<12>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states8}}}
\visible<13>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states9}}}
\visible<14>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states10}}}
\visible<15>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states11}}}
\visible<16>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states12}}}
\visible<17>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states13}}}
\visible<18>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states14}}}
\visible<19>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states15}}}
\visible<20>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states16}}}
\visible<21>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states17}}}
\visible<22>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states18}}}
\visible<23>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states19}}}
\visible<24>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states20}}}
\visible<25>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states21}}}
\visible<26>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states22}}}
\visible<27>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states23}}}
\visible<28>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states24}}}
\visible<29>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states25}}}
\visible<30->{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{states26}}}
\end{picture}
\end{frame}

\begin{frame}
\frametitle{Time and space consumptions}
\visible<2->{
\begin{block}{Lemma}
Fix $c > 0$. If $t[0..|t|-2]$ is $e$-repetition-free and $c(j - i + 1)\ge n - i$, then the states occupy $O((c + 1)(n - i))$ space.
\end{block}
}
\visible<3->{
\begin{picture}(108,18)(0,0)
\gasset{Nw=12,Nh=12,Nframe=n,AHnb=0}
\visible<3>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{space1}}}
\visible<4>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{space2}}}
\visible<5>{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{space3}}}
\visible<6->{\put(0,0){\includegraphics[scale=0.35, clip, trim=0 0 0 0]{space4}}}
\end{picture}
}
\visible<7->{Performing left extensions lazily, we can achieve $O(c)$ time for each modification of the catcher (see details in the paper)}
\end{frame}


\section{Repetition detectors}

\subsection{With backtracking}

\begin{frame}
\frametitle{Idea of the detector with backtracking}
\visible<2->{Maintain $O(\log m)$ catchers ``covering'' the string $t[0..m]$\\}
\visible<3->{
\begin{block}{Example}
\visible<3->{Fix an integer $s$ depending on $e$ (e.g. $s=3$; details in the paper)}
\begin{picture}(108,25)(0,0)
\gasset{Nw=12,Nh=12,Nframe=n,AHnb=0}
\visible<4>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system0}}}
\visible<5>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system1}}}
\visible<6>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system2}}}
\visible<7>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system3}}}
\visible<8>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system4}}}
\visible<9>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system5}}}
\visible<10>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system6}}}
\visible<11>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system7}}}
\visible<12>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system8}}}
\visible<13>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system9}}}
\visible<14>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system10}}}
\visible<15>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system11}}}
\visible<16>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system12}}}
\visible<17>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system13}}}
\visible<18>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system14}}}
\visible<19>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system15}}}
\visible<20>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system16}}}
\visible<21>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system17}}}
\visible<22>{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system18}}}
\visible<23->{\put(0,0){\includegraphics[scale=0.45, clip, trim=0 0 0 0]{system19}}}
\end{picture}
\end{block}
}
\visible<24->{
\begin{algorithmic}[1]
\State check for $e$-repetitions of length $2, 3, \ldots, s{-}1$
\For{$(k \gets 0;\; s2^k \le |t| \mathrel{\mathbf{and}} |t| \bmod 2^k = 0;\;k \gets k + 1)$}
    \If{$k > 0$}
        \State remove two catchers ``covering'' $(|t|{-}s2^k..|t|{-}(s{-}1)2^k]$
    \EndIf
    \State create a catcher ``covering'' $(|t|{-}s2^k..|t|{-}(s{-}1)2^k]$
\EndFor
\end{algorithmic}
}
\end{frame}

\begin{frame}
\frametitle{Time and space consumptions}
\pause
\begin{block}{Space}
A catcher ``covering'' a range of length $2^k$ occupies $O(2^k)$ space\\
\pause
All catchers occupy $O(\sum_{k=1}^{\log m} 2^k) = O(m)$ space\\
\end{block}
\pause
\begin{block}{Time}
The modification of a catcher takes $O(1)$ time\\
\pause
The time for the creation of the catchers is amortized over the sequence of modifications (see details in the paper)\\
\pause
The overall time is $O(n\log m)$ ($m$ is the length of a longest string generated by a given sequence of $n$ $\mathit{append}$s and $\mathit{backtrack}$s)
\end{block}
\end{frame}

\subsection{Without backtracking}

\begin{frame}
\frametitle{Idea of the detector without backtracking}
\pause
\begin{block}{Lemma}
Let $u$ be the shortest unioccurrent suffix of $t$ and $r$ be an $e$-repetition of $t$. If $t[0..|t|{-}2]$ is $e$-repetition-free, then $|u| \le |r| < \frac{e}{e - 1}|u|$.
\end{block}
\pause
Unioccurrent suffixes can be found online (without backtracking)\\
\pause
Three catchers can efficiently cover the range described in Lemma (see details in the paper)
\end{frame}

\begin{frame}
\center{\Huge{Thank you for your attention!}}
\end{frame}

\end{document}
